import java.util.*;

/**
 * @author LKQ
 * @date 2022/3/29 9:24
 * @description DFS + 邻接表 time: 14ms
 */
public class Solution {
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] arr = {4,2,3,0,3,1,2};
        solution.canReach(arr, 5);
    }
    private boolean can = false;
    /**
     * 每一个下标i可跳跃到的下标列表
     */
    List<Integer>[] lists;
    /**
     * 是否访问，防止循环
     */
    private boolean[] visited;
    public boolean canReach(int[] arr, int start) {
        int n = arr.length;
        lists = new List[n];
        visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (lists[i] == null) {
                lists[i] = new ArrayList<>();
            }
            int lo = i - arr[i], hi = i + arr[i];
            if (lo >= 0 && lo < n) {
                lists[i].add(lo);
            }
            if (hi >= 0 && hi < n) {
                lists[i].add(hi);
            }
        }
        dfs(start, arr);
        return can;
    }
    public void dfs(int start, int[] A) {
        if (A[start] == 0) {
            can = true;
            return;
        }
        if (can) {
            return;
        }
        if (visited[start]) {
            return;
        }
        visited[start] = true;
        for (int y: lists[start]) {
            dfs(y, A);
        }
        visited[start] = false;
    }
}
